package com.linyaonan.leetcode.medium._1170;

import java.util.Arrays;

/**
 * 定义一个函数 f(s)，统计 s  中（按字典序比较）最小字母的出现频次 ，其中 s 是一个非空字符串。
 *
 * 例如，若 s = "dcce"，那么 f(s) = 2，因为字典序最小字母是 "c"，它出现了 2 次。
 *
 * 现在，给你两个字符串数组待查表 queries 和词汇表 words 。对于每次查询 queries[i] ，需统计 words 中满足 f(queries[i]) < f(W) 的 词的数目 ，W 表示词汇表 words 中的每个词。
 *
 * 请你返回一个整数数组 answer 作为答案，其中每个 answer[i] 是第 i 次查询的结果。
 *
 *
 *
 * 示例 1：
 *
 * 输入：queries = ["cbd"], words = ["zaaaz"]
 * 输出：[1]
 * 解释：查询 f("cbd") = 1，而 f("zaaaz") = 3 所以 f("cbd") < f("zaaaz")。
 * 示例 2：
 *
 * 输入：queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
 * 输出：[1,2]
 * 解释：第一个查询 f("bbb") < f("aaaa")，第二个查询 f("aaa") 和 f("aaaa") 都 > f("cc")。
 *
 *
 * 提示：
 *
 * 1 <= queries.length <= 2000
 * 1 <= words.length <= 2000
 * 1 <= queries[i].length, words[i].length <= 10
 * queries[i][j]、words[i][j] 都由小写英文字母组成
 *
 * @author: Lin
 * @date: 2024/12/2
 */
public class CompareStringsByFrequencyOfTheSmallestCharacter {

    /**
     * queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
     *
     * queries = 3,2 words = 1,2,3,4
     *
     *
     * 将words进行升序排序，queries进行最左匹配大于等于目标值，然后返回长度（4） - index（3）
     *
     *
     * @param queries
     * @param words
     * @return
     */
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] queries_int = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            queries_int[i] = getNumFromStr(queries[i]);
        }
        int[] words_int = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            words_int[i] = getNumFromStr(words[i]);
        }

        Arrays.sort(words_int);
        int words_len = words_int.length;
        for (int i = 0; i < queries_int.length; i++) {
            queries_int[i] = words_len - check(words_int, queries_int[i]);
        }
        return queries_int;
    }

    public int getNumFromStr(String str) {
        int[] c = new int[26];
        for (int i = 0; i < str.length(); i++) {
            c[str.charAt(i) - 'a']++;
        }
        //
        for (int i = 0; i < c.length; i++) {
            if (c[i] > 0) {
                return c[i];
            }
        }
        return 0;
    }

    public int check(int[] nums, int t) {
        int l = 0;
        int r = nums.length - 1;
        int tt = nums.length;
        while (l <= r) {
            int m = (l + r) >>> 1;
            int temp = nums[m];
            if (temp > t) {
                tt = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return tt;
    }

}
